{-# OPTIONS_GHC -fglasgow-exts #-}
 
module Main where
import Control.Monad (guard, liftM2)
import Control.Monad.Instances
import Data.List (elemIndex)
import Data.Array.Unboxed
import Data.Maybe
import qualified Data.Set as S
import qualified Data.Map as M
import qualified Data.PQueue.Prio.Min as Q
 
newtype Point = Point (Int, Int) deriving (Eq, Show, Read, Ix)
instance Ord Point where
  compare (Point (x,y)) (Point (z,t)) = compare (y,x) (t,z)

type Map = UArray Point Char
 
find :: Char -> Map -> Maybe Point
find c m = find' m (reverse.indices $ m)
 where find' _ [] = Nothing
       find' m (h:t)
        | c == (m ! h) = Just h
        | otherwise = find' m t
 
heuristic :: Point -> Point -> Int
heuristic (Point (x, y)) (Point (u, v)) = abs (x - u) `max` abs (y - v)
 
successor :: Int -> Int -> Map -> Point -> [Point]
successor nL nC m (Point (x,y)) = do u <- [x + 1, x, x - 1]
                                     v <- [y + 1, y, y - 1]
                                     guard (0 < u && u <= nL)
                                     guard (0 < v && v <= nC)
                                     guard (u /= x || y /= v)
                                     guard (u == x || y == v)
                                     guard ((m ! (Point (u, v))) /= 'L')
                                     guard ((m ! (Point (u, v))) /= '#')
                                     guard ((m ! (Point (u, v))) /= '*')
                                     guard.not $ (v < nC && (m ! (Point (u, v))) == ' ' && (m ! (Point (u, v + 1))) == '*')
                                     return (Point (u, v))

astar :: Point -> (Point -> [Point]) -> (Point -> Bool) -> (Point -> Int) -> (Point -> Int) -> [Point]
astar start succ end cost heur = astar' (S.singleton start) (Q.singleton (heur start) [start])
 where
 astar' seen q
    | Q.null q  = error "No Solution."
    | end n     = next
    | otherwise = astar' seen' q'
  where
  ((c,next), dq) = Q.deleteFindMin q
  n     = head next
  succs = filter (`S.notMember` seen) $ succ n
  costs = map ((+ c) . (subtract $ heur n) . liftM2 (+) cost heur) succs
  q'    = dq `Q.union` Q.fromList (zip costs (map (:next) succs))
  seen' = seen `S.union` S.fromList succs
 
path :: Point -> [Point] -> String
path s l = path' s l
 where path' _ [] = ""
       path' p1@(Point (x,y)) (p2@(Point (z,t)):xs) =
	     (if p1 == p2
	        then 'W'
            else if z == (x+1)
                   then 'R'
                   else if z == (x-1)
                          then 'L'
                          else if t == (y+1)
                                 then 'U'
                                 else 'D') : path' p2 xs

fullPath :: Point -> (Point -> [Point]) -> Point -> (Point -> Int) -> (Point -> Int) -> Map -> Bool -> [Point]
fullPath start succ endPoint cost heur maps toLambda =
  if (not toLambda)
    then current
    else current ++ followings
  where current = astar start succ (== endPoint) cost heur
        (nextEnd,toLambda') = maybe (maybe (error "No end point...peculiar that") (\x -> (x, False)) $ find 'O' maps) (\x -> (x, True)) $ find '\\' maps
        followings = fullPath endPoint succ nextEnd cost h maps toLambda'
        h = heuristic nextEnd

doit :: String -> String
doit s = path start $ fullPath start succ end cost h m toLambda
 where linesM = takeWhile (/= "") (lines s)
       nLines = length (head linesM)
       nCol   = length linesM
       m      = listArray ((Point (1,1)),(Point (nLines,nCol))) (concat linesM)
       start  = fromMaybe (error "No starting point...peculiar that") $ find 'R' m
       (end,toLambda) = maybe (maybe (error "No end point...peculiar that") (\x -> (x, False)) $ find 'O' m) (\x -> (x, True)) $ find '\\' m
       succ   = successor nLines nCol m
       h      = heuristic end
       cost   = const 1
 
main = interact doit